package com.example.code2022;

import com.alibaba.fastjson.JSON;

import java.util.Random;

/**
 * @author: dangwen
 * @createDate: 2022/4/23
 * 912. 排序数组
 * 给你一个整数数组 nums，请你将该数组升序排列。
 */
public class P912 {

    public static void main(String[] args) {
        int[] nums = new int[]{5,1,1,2,0,0};
//        mergerSort(nums, 0, nums.length - 1, new int[nums.length]);
//        System.out.println(JSON.toJSONString(nums));
        sort(nums, 0 , nums.length - 1);
        System.out.println(JSON.toJSONString(nums));
    }

    // 归并排序
    public static void mergeSort(int[] nums, int lo, int hi, int[] temp){
        if (lo >= hi){
            return;
        }
        int mid = lo + (hi - lo) / 2;
        mergeSort(nums, lo, mid, temp);
        mergeSort(nums,mid + 1, hi, temp);

        merge(nums,lo,mid,hi,temp);
    }

    private static void merge(int[] nums, int lo, int mid, int hi, int[] temp) {
        // 数组拷贝
        for (int i = lo; i <= hi;i++){
            temp[i] = nums[i];
        }
        int i = lo;
        int j = mid + 1;
        for (int k = lo; k <= hi; k++){
            if (i == mid + 1){
                nums[k] = temp[j++];
            } else if (j == hi + 1){
                nums[k] = temp[i++];
            } else if (temp[i] < temp[j]){
                nums[k] = temp[i++];
            } else {
                nums[k] = temp[j++];
            }
        }
    }

    // 快速排序：两路快排
    public static void quickSort(int[] nums, int lo, int hi){
        if (lo >= hi){
            return;
        }
        // 分区的目的是把小于pivot的放在左边，大于pivot的放在右边
        int index = partition(nums, lo, hi);
        quickSort(nums, lo, index - 1);
        quickSort(nums, index + 1, hi);
    }

    private static int partition(int[] nums, int lo, int hi) {
        // 为了防止链表是有序的，排序时间为最差：取随机值作为pivot
        int randomIndex = new Random().nextInt(hi - lo + 1) + lo;
        // 将pivot放到最后（一般pivot会选最后一个元素）
        swap(nums, randomIndex, hi);
        int pivot = nums[hi];
        // 分区逻辑核心：双指针，great指针指向的元素和pivot元素比较，小于pivot的和less进行交换，less右移，great到pivot前一位停止
        int less = 0;
        int great = 0;
        for (; great < hi; great++){
            if (nums[great] < pivot){
                swap(nums, less, great);
                less++;
            }
        }
        // 最后，pivot需要和less进行对换
        swap(nums, less, hi);
        return less;
    }

    private static void swap(int[] nums, int pivot, int hi) {
        int temp = nums[pivot];
        nums[pivot] = nums[hi];
        nums[hi] = temp;
    }

    // 三路快排
    public static void sort(int[] nums, int lo, int hi){
        if (lo >= hi){
            return;
        }
        int pivot = nums[hi];
        int less = lo;
        int great = hi;
        int i = lo;
        while (i <= great){
            if (nums[i] < pivot){
                swap(nums, less, i);
                less++;
                i++;
            } else if (nums[i] > pivot){
                swap(nums, i, hi);
                great--;
            } else {
                i++;
            }
        }

        sort(nums, lo, less - 1);
        sort(nums, great + 1 ,hi);
    }



}
